public class Solution221 {
    public int maximalSquare(char[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        int[][] sum=new int[m+1][n+1];
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                sum[i][j]=sum[i-1][j]+sum[i][j-1]+matrix[i-1][j-1]-'0'-sum[i-1][j-1];
            }
        }
        int max=0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (matrix[i][j]=='1'){
                    for (int k=0;j+k<n & i+k<m;k++){
                        int f=sum[i+k+1][j+k+1]-sum[i+k+1][j]-sum[i][j+k+1]+sum[i][j];
                        if (f!=(k+1)*(k+1)){
                            break;
                        }
                        max=Math.max(max,f);
                    }
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new Solution221().maximalSquare(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}));
    }
}
